package com.googlecode.gaal.suffix.impl;

import com.googlecode.gaal.data.api.IntSequence;
import com.googlecode.gaal.suffix.algorithm.api.LcpTableBuilder;
import com.googlecode.gaal.suffix.algorithm.api.SuffixTableBuilder;
import com.googlecode.gaal.suffix.api.SuffixArray;

public abstract class SuffixArrayBase implements SuffixArray {
    protected final IntSequence sequence;
    protected final int alphabetSize;
    protected final int[] suffixTable;
    protected final int[] lcpTable;
    protected int[] inverseSuffixTable;

    public SuffixArrayBase(IntSequence sequence, int alphabetSize, int[] suffixTable, int[] lcpTable) {
        this.sequence = sequence;
        this.alphabetSize = alphabetSize;
        this.suffixTable = suffixTable;
        this.lcpTable = lcpTable;
    }

    public SuffixArrayBase(IntSequence sequence, int alphabetSize, SuffixTableBuilder suffixTableBuilder,
            LcpTableBuilder lcpTableBuilder) {
        this.sequence = sequence;
        this.alphabetSize = alphabetSize;
        this.suffixTable = suffixTableBuilder.buildSuffixTable(sequence, alphabetSize);
        this.lcpTable = lcpTableBuilder.buildLcpTable(suffixTable, sequence);
    }

    @Override
    public IntSequence getSequence() {
        return sequence;
    }

    @Override
    public int[] getSuffixTable() {
        return suffixTable;
    }

    @Override
    public int[] getInverseSuffixTable() {
        if (inverseSuffixTable == null) {
            inverseSuffixTable = new int[suffixTable.length];
            for (int i = 0; i < suffixTable.length; i++) {
                inverseSuffixTable[suffixTable[i]] = i;
            }
        }
        return inverseSuffixTable;
    }

    @Override
    public int[] getLcpTable() {
        return lcpTable;
    }

    @Override
    public int alphabetSize() {
        return alphabetSize;
    }

    public int search(int token) {
        return search(token, 0, suffixTable.length - 1);
    }

    public int search(int token, int start, int end) {
        if (start == end - 1)
            return start;
        int mid = start + (end - start) / 2;
        if (token < sequence.get(suffixTable[mid])) {
            return search(token, start, mid - 1);
        } else {
            return search(token, mid, end);
        }
    }
}
